package com.longge;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-03-09 00:39
 */
public class IsSubStructure {
    List<TreeNode> treeNodes = new ArrayList<>();

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        dfs(A, B.val);
        for (TreeNode subA : treeNodes) {
            if (compare(subA, B)) return true;
        }
        return false;
    }

    private boolean compare(TreeNode subA, TreeNode b) {
        if (subA == null && b == null) return true;
        if (subA == null) return false;
        if (b == null) return true;
        if (subA.val != b.val) return false;
        return compare(subA.left, b.left) && compare(subA.right, b.right);
    }

    private void dfs(TreeNode root, int val) {
        if (root == null) return;
        if (root.val == val) {
            treeNodes.add(root);
        }
        dfs(root.left, val);
        dfs(root.right, val);


    }
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        TreeNode treeNode5 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(2);
        treeNode5.left=treeNode6;

        new IsSubStructure().isSubStructure(treeNode1,treeNode5);
    }
}
